package demo3;

import java.util.*;
class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    //1.奇偶链表(维护双指针法)
/*    public ListNode oddEvenList(ListNode head) {
        if(head == null) {
            return head;
        }
        //维护双链表发:一个链表用来维护奇数，另一个链表用来维护偶数
        ListNode j_node = new ListNode();//奇数
        ListNode o_node = new ListNode();//偶数
        ListNode j_cur = j_node;
        ListNode o_cur = o_node;
        int count = 1;//计数器确定奇偶
        //记录第一个结点的奇偶性
        int ans = head.val;
        while(head != null) {
            if(count % 2 != 0) {
                j_cur.next = head;
                j_cur = head;
            }else {
                o_cur.next = head;
                o_cur = head;
            }
            count++;
            head = head.next;
        }
        j_cur.next = o_node.next;
        o_cur.next = null;
        return j_node.next;
    }*/
    //1.奇偶链表(维护双指针法(优化))
    public ListNode oddEvenList(ListNode head) {
        if(head == null) {
            return head;
        }
        ListNode headTail = head;//奇链表的尾
        ListNode oHead = head.next;//偶链表的头
        ListNode oTail = oHead;//偶链表的尾巴
        while(headTail.next != null && oTail.next != null) {
            headTail.next = oTail.next;
            headTail = oTail.next;
            oTail.next = headTail.next;
            oTail = headTail.next;
        }
        headTail.next = oHead;
        return head;
    }
    //两数相加 II(栈)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //栈
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        //将两个链表全部入栈
        while(cur1 != null) {
            stack1.push(cur1);
            cur1 = cur1.next;
        }
        while(cur2 != null) {
            stack2.push(cur2);
            cur2 = cur2.next;
        }
        int ans = 0;//控制进位
        //取出逐个相加到l1
        while(!stack1.isEmpty() || !stack2.isEmpty()) {
            //若有任意一个为空，则用0来占位
            if(stack1.isEmpty()) {
                ListNode tmp = new ListNode(0);
                tmp.next = cur1;
                stack1.push(tmp);
            }else if(stack2.isEmpty()) {
                ListNode tmp = new ListNode(0);
                tmp.next = cur2;
                stack2.push(tmp);
            }
            cur1 = stack1.pop();
            cur2 = stack2.pop();
            int sum = cur1.val + cur2.val + ans;
            cur1.val = sum % 10;
            ans = sum / 10;
        }
        if(ans == 1) {
            ListNode head = new ListNode(1);
            head.next = cur1;
            return head;
        }
        return cur1;
    }
    //2.面试题 02.02. 返回倒数第 k 个节点(快慢指针)
    public int kthToLast(ListNode head, int k) {
        //快慢指针法
        ListNode fast = head;
        ListNode slow = head;
        //先让快指针走k步
        for(int i = 0; i < k; i++) {
            fast = fast.next;
        }
        //然后快慢指针一起走，快指针为空，慢指针即为所求
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
    //3.二进制链表转整数(直接转化)
    public int getDecimalValue(ListNode head) {
        ListNode cur = head;
        //求链表长度
        int len = 0;
        while(cur != null) {
            cur = cur.next;
            len++;
        }
        int sum = 0;
        cur = head;
        while(cur != null) {
            len--;//使其表示该加上2的几次方
            sum += cur.val * Math.pow(2, len);
            cur = cur.next;
        }
        return sum;
    }
    //3.二进制链表转整数(反推优化)
    public int getDecimalValue(ListNode head) {
        //反推5/2的余数 = 商 * 除数 + 余数
        ListNode cur = head;
        int sum = 0;
        while(cur != null) {
            sum = sum*2 + cur.val;
            cur = cur.next;
        }
        return sum;
    }
    //4.面试题 02.07. 链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //先计算出两链表的长
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int len1 = 0;
        int len2 = 0;
        while(cur1 != null) {
            cur1 = cur1.next;
            len1++;
        }
        while(cur2 != null) {
            cur2 = cur2.next;
            len2++;
        }
        cur1 = headA;
        cur2 = headB;
        //让长的链表的先走差值步，然后同时走
        if(len1 > len2) {
            int ans = len1 - len2;
            for(int i = 0; i < ans; i++) {
                cur1 = cur1.next;
            }
            while(cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }else {
            int ans = len2 - len1;
            for(int i = 0; i < ans; i++) {
                cur2 = cur2.next;
            }
            while(cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }
        return cur1;
    }
    //5.面试题 02.01. 移除重复节点(哈希)
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        Set<Integer> set = new HashSet<>();
        set.add(head.val);
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null) {
            if(!set.contains(cur.val)) {
                set.add(cur.val);
            }else {
                //删除结点
                prev.next = cur.next;
                cur.next = null;
                cur = prev;
            }
            prev = cur;
            cur = cur.next;
        }
        return head;
    }
    //5.面试题 02.01. 移除重复节点(哈希优化)
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null) {
            return head;
        }
        Set<Integer> set = new HashSet<>();
        ListNode cur = head;
        set.add(cur.val);
        while(cur.next != null) {
            ListNode del = cur.next;//待删除的结点
            if(set.add(del.val)) {
                cur = cur.next;
            }else {
                cur.next = cur.next.next;
            }
        }
        return head;
    }
    //6.面试题 02.03. 删除中间节点
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
    //7.面试题 02.05. 链表求和
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        int ans = 0;//进位
        //让l1作为被加链表
        while(cur1 != null || cur2 != null) {
            if(cur1.next == null && cur2.next != null) {
                ListNode node = new ListNode(0);
                cur1.next = node;
            }
            if(cur2.next == null && cur1.next != null) {
                ListNode node= new ListNode(0);
                cur2.next = node;
            }
            int sum = cur1.val + cur2.val + ans;
            ans = sum / 10;
            cur1.val = sum % 10;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        if(ans == 1) {
            cur1 = l1;
            while(cur1.next != null) {
                cur1 = cur1.next;
            }
            ListNode node = new ListNode(1);
            cur1.next = node;
        }
        return l1;
    }

    //8.面试题 02.06. 回文链表(官方解法)
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        //快慢指针
        //先找到后半段的开头的指针
        ListNode halfStart = findHalfStart(head);
        //反转后半段
        ListNode p2 = reversList(halfStart.next);
        ListNode p1 = head;
        while(p2 != null) {
            if(p2.val != p1.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
    //反转链表
    private ListNode reversList(ListNode halfStart) {
        ListNode prev = null;
        ListNode cur = halfStart;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
    private ListNode findHalfStart(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //9.剑指 Offer II 078. 合并排序链表
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        //他的前提是合并两个有序链表
        for(int i = 0; i < lists.length; i++) {
            ans = merge(ans, lists[i]);
        }
        return ans;
    }
    public ListNode merge(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            }else{
                tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            }
        }
        if(list1 == null){
            tmp.next = list2;
        }
        else{
            tmp.next = list1;
        }
        return newHead.next;
    }
    //10.剑指 Offer II 024. 反转链表(自身修改)
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
}
//设计链表(双向链表)

class MyLinkedList {
    class ListNode {
        private ListNode prev;
        private ListNode next;
        private int val;
        ListNode(int val) {
            this.val = val;
        }
    }
    private int size = 0;
    private ListNode head;
    private ListNode tail;
    //获取链表中第 index个节点的值。如果索引无效，则返回-1。
    public int get(int index) {
        if(index < 0 || index > size) {
            return -1;
        }
        ListNode cur = head;
        for(int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }
    //在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
    public void addAtHead(int val) {
        if(head == null) {
            head = new ListNode(val);
            tail = head;
        }else {
            ListNode node = new ListNode(val);
            node.next = head;
            head = node;
        }
        size++;
    }
    //将值为 val 的节点追加到链表的最后一个元素。
    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        tail.next = node;
        tail = node;
        size++;
    }
    //在链表中的第index个节点之前添加值为val 的节点。
    // 如果index等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，
    // 则不会插入节点。如果index小于0，则在头部插入节点。
    public void addAtIndex(int index, int val) {
        ListNode node = new ListNode(val);
        if(index == size) {
            tail.next = node;
            tail = node;
        }else if(index > size){
            return;
        }else if(index > 0 && index < size){
            ListNode cur = head;
            for(int i = 0; i < index; i++) {
                cur = cur.next;
            }
            node.next = cur;
            node.prev = cur.prev;
            cur.prev.next = node;
            cur.prev = node;
        }else{
            node.next = head;
            head = node;
        }
        size++;
    }
    //如果索引 index 有效，则删除链表中的第 index 个节点。
    public void deleteAtIndex(int index) {
        if(index < 0 || index > size) {
            return;
        }
        ListNode cur = head;
        for(int i = 0; i < index; i++) {
            cur = cur.next;
        }
        if(cur == head) {
            head = head.next;
            head.prev = null;
        }else if(cur == tail) {
            tail = tail.prev;
            tail.next = null;
        }else{
            cur.prev = cur.next;
            cur.next.prev = cur.prev;
        }
    }
}
